/***************************************************
 * intro121/ipis121: Third assignment              *
 *                                                 *
 * This class is for assignment #3 - Part 3        *
 *                                                 *
 * Author(s): ### YOUR NAME(S) AND EMAIL(S). ##### *
 * Date: ##/##/####                                *
 *                                                 *
 ***************************************************/

/*
 * Important! Add comments to every method!
 *
 * The "return" statement at the end of each method and the initial value 
 * is just so this skeleton file compiles, change it according to your needs
 */

public class Ex3 {

	public static int north(int[] tile){
		return tile[0];
	}

	public static int east(int[] tile){
		return tile[1];
	}

	public static int south(int[] tile){
		return tile[2];
	}

	public static int west(int[] tile){
		return tile[3];
	}


	/******************** Task 1 ********************/
	public static boolean canPut(int[]tile, int x, int y, int[][][] board) {
		boolean ans = true;
		if (board[x][y]!=null)  // if space at board[x][y] already taken
			ans=false;			// new Tile cannot be put at an already token space
		else
		{
			if (y==0)													//if there is the board wall north of new Tile
			{
				ans = (north(tile)==0);									//true if color 0
			}
			else
			{
				if(ans==true)
					ans = (north(tile)!=0);
				if(ans==true)
					if(board[x][y-1]!=null)								//if there is a tile north of new Tile
						ans = (north(tile)==south(board[x][y-1]));		
			}
			if (y==board[x].length-1 && ans==true)						//if there is the board wall south of new Tile
			{
				ans = (south(tile)==0);								//true if color 0
			}
			else
			{
				if(ans==true)
					
					ans = (south(tile)!=0);
				if(ans==true)
					if(board[x][y+1]!=null)								//if there is a tile south of new Tile

						ans = (south(tile)==north(board[x][y+1]));
			}	
			if (x==0 && ans==true)										//if there is the board wall west of new Tile
			{
				ans = (west(tile)==0);									//true if color 0
			}
			else
			{
				if(ans==true)
					ans = (west(tile)!=0);	
				if(ans==true)
					if(board[x-1][y]!=null)								//if there is a tile west of new Tile
						ans = (west(tile)==east(board[x-1][y]));		
			}
			if (x==board.length-1 && ans==true)							//if there is the board wall east of new Tile
			{
				ans = (east(tile)==0);									//true if color 0
			}
			else
			{
				if(ans==true)
					ans = (east(tile)!=0);
				if(ans==true)										//
					if(board[x+1][y]!=null)								//if there is a tile east of new Tile
						ans = (east(tile)==west(board[x+1][y]));
			}	
				//ans = (north(tile)==south(board[x][y-1]) && east(tile)==west(board[x+1][y]) && south(tile)==north(board[x][y+1]) && west(tile)==east(board[x-1][y]) );
			
		}
		return ans;
	}



	/******************** Task 2 ********************/
	public static int[][][] put(int[] tile, int x, int y, int[][][] board) {
		int n = board.length;
		int[][][] newBoard= new int[n][n][];
		for (int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				if(board[i][j]!=null)			// if there is a tile at board column i row j
				{
					newBoard[i][j]=new int[4];				
					for(int m=0;m<4;m++)
						newBoard[i][j][m]=board[i][j][m];   //copy tile to newBoard
				}
		newBoard[x][y]=tile;								//put the pointer to the new tile in newBoard at column x row y
		return newBoard;
	}



	/******************** Task 3 ********************/
	public static int[][] delete(int i, int[][] tiles) {
		int[][] restTiles = new int[tiles.length-1][4];
		for(int j=0;j<tiles.length;j++)//loop through tiles bank
		{
			if(j<i) //if we are before deletion index then put tile into new tile bank
			{
				restTiles[j]=tiles[j];
			}
			if(j>i)//if we are afte deletion index then put tile into new tile bank in earlier position
			{
				restTiles[j-1]=tiles[j];
			}
		}
		return restTiles;
	}

	public static int[] rotate(int j, int[] tile){
		int[] nextTile = new int[4];
		if(j<=3 && j>0 && tile != null) //input validation
		{
			for(int i=0;i<=3;i++) //loop through 4 sides
			{
				nextTile[(i+j)%4]=tile[i]; //rotate j spots
			}
			return nextTile;	
		}
		else
		{
			return null;
		}
	}



	/******************** Task 4 ********************/
	public static int[][][] solve(int[][] tiles){
		int size = (int) Math.sqrt(tiles.length);
		int[][][] board = new int[size][size][];
		return solve(board,tiles);
	}

	public static int[][][] solve(int[][][] board, int[][] tiles){
		int[][][] solution = null;
		int i=0;
		int j=0;
		while(i<board.length && j< board.length && board[i][j]!=null)//find the next empty place for tiles
		{
			j++;
			if(j==board.length)
			{
				j=0;
				i++;
			}
		}	
		for(int k=0;k<tiles.length && tiles.length>0;k++)//loop through tiles bank
		{
			for(int r=0;r<=3;r++)//loop through possible rotations
			{
				if(tiles[k]!=null && canPut(tiles[k],i,j,board)) //see if we can put the tile in empty place
				{
					int[][] tempTiles = new int[tiles.length-1][4];
					int[][][] tempBoard = new int[board.length][board.length][4];
					tempBoard = put(tiles[k],i,j,board); 
					tempTiles = delete(k,tiles);
					//showTemp(tempBoard); //show us the state
					if (tempTiles.length==0)//we solved the board, prevents needles call to function on solved board
					{
						return tempBoard;
					}
					else
					{
						solution=solve(tempBoard,tempTiles); //call solve with some placed tiles attempt
					}
					if(solution!=null)//we got a good solution from recursive call and solved the board
					{
						return solution;
					}
							
							
				}
				tiles[k]=rotate(1,tiles[k]);//try with flipped tile
			}
		}		
		return solution;
	}
	
	
	
	
	
	
	
	
 public static void showTemp(int[][][] board)
 {
	 int[][][] solution =new int[board.length][board.length][4];
	 for (int i=0;i<board.length;i++)
	 {
		for(int j=0;j<board.length;j++)
		{
			if(board[i][j]!=null)
			{
				solution[i][j]=board[i][j];
			}
		}
	 }
	 //EternityPrint.showBoard(solution);
 }
	/******************** Auxiliary functions ********************/
	
	/**
	 * Compare two boards and return true iff they are equal.
	 * @param board1
	 * @param board2
	 * @return true iff the boards are equal
	 */
	public static boolean equalBoards(int[][][] board1, int[][][] board2) {
		boolean ans = true;
		for (int i = 0; i < board1.length && ans; i++) {
			for (int j = 0; j < board1.length && ans; j++) {
				int[] tile1 = board1[i][j];
				int[] tile2 = board2[i][j];
				if ((tile1 == null && tile2 != null)
						|| (tile1 != null && tile2 == null))
					ans = false;
				else if (tile1 != null && tile2 != null) {
					for (int k = 0; k < 4 && ans; k++)
						if (tile1[k] != tile2[k])
							ans = false;
				}
			}
		}
		return ans;
	}


	public static void main(String[] args) {
		int[][][] board = { { { 0, 2, 1, 0 }, null, { 1, 3, 0, 0 } },
				{ { 0, 2, 4, 2 }, null, { 4, 4, 0, 3 } },
				{ { 0, 0, 4, 2 }, { 4, 0, 3, 3 }, { 3, 0, 0, 4 } } };

		// Test task 1
		int[] test1tile = {1, 2, 1, 0};
		System.out.println("Test 1: expected=true actual="
				+ canPut(test1tile, 0, 1, board));

		int[] test2tile = {2, 2, 1, 0};
		System.out.println("Test 2: expected=false actual="
				+ canPut(test2tile, 0, 1, board));

		int[] test3tile = {1, 2, 1, 1};
		System.out.println("Test 3: expected=false actual="
				+ canPut(test3tile, 0, 1, board));

		// Test task 2
		int[] test4tile = {1, 2, 1, 0};
		int[][][] test4exp = { { { 0, 2, 1, 0 }, { 1, 2, 1, 0 }, { 1, 3, 0, 0 } },
				{ { 0, 2, 4, 2 }, null, { 4, 4, 0, 3 } },
				{ { 0, 0, 4, 2 }, { 4, 0, 3, 3 }, { 3, 0, 0, 4 } } };
		System.out.println("Test 4: "
				+ (equalBoards(test4exp, put(test4tile, 0, 1, board)) ? "passed :)"
						: "failed!"));
		
		// Test task 3
		int[] test5tile= {1, 2, 3, 4};
		int[] test5exp = {4, 1, 2, 3};
		System.out.println("Test 5: expected=" + Ex2.arrayToString(test5exp)  + 
				" actual=" + Ex2.arrayToString(rotate(1, test5tile)));
		
		int[] test6tile= {1, 2, 3, 4};
		int[] test6exp = {3, 4, 1, 2};
		System.out.println("Test 6: expected=" + Ex2.arrayToString(test6exp)  + 
				" actual=" + Ex2.arrayToString(rotate(2, test6tile)));
		
		int[][] test7tiles = {{1, 2, 3, 4}, {0, 2, 4, 5}, {5, 2, 5, 1}};
		int[][] test7exp = {{1, 2, 3, 4}, {5, 2, 5, 1}};
		System.out.println("Test 7: expected=" + Ex2.matrixToString(test7exp)  + 
				" actual=" + Ex2.matrixToString(delete(1, test7tiles)));
		int[][] tiles ={{3,1,0,2},{3,2,0,1},{2,0,0,2},{0,2,1,0},{0,0,1,1},{1,3,1,0},{4,4,3,3},{2,0,2,3},{3,3,3,4},{1,2,0,0},{1,4,1,0},{0,2,4,2},{0,1,4,2},{4,3,4,4},{4,4,3,3},{1,0,2,4}};
		int[][][] solution = solve(tiles);
		//int[][][] test = new int[4][4][4];
		if(solution!=null)
			System.out.println("done!");
		//System.out.println("done!");
		//EternityPrint.showBoard(solution);
		int[][] tiles2={{0,1,3,2},{0,0,2,2},{0,2,1,0},{3,1,0,2},{0,0,1,1},{1,3,1,0},{4,4,3,3},{2,0,2,3},{3,3,3,4},{0,0,1,2},{1,4,1,0},{0,2,4,2},{0,1,4,2},{4,3,4,4},{4,4,3,3},{1,0,2,4}};
		int[][][] solution2 = solve(tiles2);
		//EternityPrint.showBoard(solution2);
		if(solution2!=null)
			System.out.println("done!");
		int[][] tiles3 = {{2,0,2,3},{3,3,3,4},{0,0,1,2},{1,4,1,0}};
		int[][][] solution3 = solve(tiles3);
		if(solution3!=null)
			System.out.println("done!");
		//EternityPrint.showBoard(solution3);
			
	}
}
